package LeetCode;

public class LC_215_KthLargestElementinanArray {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            if (k < 1 || nums == null || nums.length < k) throw new IllegalArgumentException();
            return findKthLargest(nums, 0, nums.length - 1, k);
        }

        private int findKthLargest(int[] nums, int start, int end, int k) {
            int pivot = nums[start];
            int lo = start;
            int hi = end;
            while (lo < hi) {
                while (lo < hi && nums[hi] >= pivot) hi--;
                nums[lo] = nums[hi];
                while (lo < hi && nums[lo] <= pivot) lo++;
                nums[hi] = nums[lo];
            }
            nums[lo] = pivot;
            if (end - lo + 1 == k) return pivot;
            else if (end - lo + 1 > k) return findKthLargest(nums, lo + 1, end, k);
            else return findKthLargest(nums, start, lo - 1, k - (end - lo + 1));
        }

    }
}